package com.leetcode.No1774;

import org.junit.Test;

import java.util.Arrays;

/**
 * @program: Solution
 * @description: 最接近目标价格的甜点成本
 * @author: Wang Zhihua
 * @date: 2022-12-05
 */
public class Solution {
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        int n = baseCosts.length;
        int m = toppingCosts.length;
        Arrays.sort(baseCosts);
        Arrays.sort(toppingCosts);

        int gap = Integer.MAX_VALUE;
        int result = 0;
        int maxLen = getMaxLen(n, m);
        int[] sum = new int[maxLen];
        int sumSize = 0;

        for (int baseCost : baseCosts) {
            sum[sumSize++] = baseCost;
        }
        for (int toppingCost : toppingCosts) {
            int originSize = sumSize;
            for (int i = 1; i <= 2; ++i) {
                int tmpToppingCost = toppingCost * i;
                for (int j = 0; j < originSize; ++j) {
                    sum[j + sumSize] = sum[j] + tmpToppingCost;
                }
                sumSize += originSize;
            }
        }

        for (int i = 0; i < sumSize; ++i) {
            int tmpGap = Math.abs(target - sum[i]);
            if (tmpGap == 0) {
                return sum[i];
            }
            if (tmpGap < gap) {
                gap = tmpGap;
                result = sum[i];
            } else if (tmpGap == gap) {
                result = Math.min(sum[i], result);
            }
        }

        return result;
    }

    private int getMaxLen(int n, int m) {
        int result = n;
        while(m-- > 0) {
            result *= 3;
        }
        return result;
    }

    @Test
    public void test01() {
        int[] baseCosts;
        int[] toppingCosts;
        int target;

        baseCosts = new int[]{1,7};
        toppingCosts = new int[]{3,4};
        target = 10;
        System.out.println(closestCost(baseCosts, toppingCosts, target));

        baseCosts = new int[]{2,3};
        toppingCosts = new int[]{4,5,100};
        target = 18;
        System.out.println(closestCost(baseCosts, toppingCosts, target));

        baseCosts = new int[]{3,10};
        toppingCosts = new int[]{2,5};
        target = 9;
        System.out.println(closestCost(baseCosts, toppingCosts, target));
    }
}
